/* eslint-disable no-console */
/* eslint-disable @typescript-eslint/no-inferrable-types */
/* eslint-disable @typescript-eslint/quotes */
/* eslint-disable arrow-parens */
/* ---------------------------------------------------------------------------------------------
 *  Copyright (c) Microsoft Corporation. All rights reserved.
 *  Licensed under the MIT License. See License.txt in the project root for license information.
 *--------------------------------------------------------------------------------------------*/

import { Disposable, Emitter, debounce } from '../../utils';

import { Color, RGBA } from './terminal.typeAhead.ext';
import { IXtermCore, XtermAttributes } from './xterm-private';

import type { IBuffer, IBufferCell, IDisposable, Terminal } from '@xterm/xterm';

export interface ITerminalConfiguration {
  localEchoEnabled: 'auto' | 'on' | 'off';
  localEchoStyle:
    | 'bold'
    | 'dim'
    | 'italic'
    | 'underlined'
    | 'inverted'
    | string;
}

const ESC = '\x1b';
const CSI = `${ESC}[`;
const SHOW_CURSOR = `${CSI}?25h`;
const HIDE_CURSOR = `${CSI}?25l`;
const DELETE_CHAR = `${CSI}X`;
const DELETE_REST_OF_LINE = `${CSI}K`;
const CSI_STYLE_RE = /^\x1b\[[0-9;]*m/;
const CSI_MOVE_RE = /^\x1b\[?([0-9]*)(;[35])?O?([DC])/;
const NOT_WORD_RE = /[^a-z0-9]/i;

const statsBufferSize = 24;

/**
 * Codes that should be omitted from sending to the prediction engine and instead omitted directly:
 * - Hide cursor (DECTCEM): We wrap the local echo sequence in hide and show
 *   CSI ? 2 5 l
 * - Show cursor (DECTCEM): We wrap the local echo sequence in hide and show
 *   CSI ? 2 5 h
 * - Device Status Report (DSR): These sequence fire report events from xterm which could cause
 *   double reporting and potentially a stack overflow (#119472)
 *   CSI Ps n
 *   CSI ? Ps n
 */
const PREDICTION_OMIT_RE = /^(\x1b\[(\??25[hl]|\??[0-9;]+n))+/;

const core = (terminal: Terminal): IXtermCore => (terminal as any)._core;
const flushOutput = (terminal: Terminal) => {
  // TODO: Flushing output is not possible anymore without async
};

// 本地变量控制是否打开Log，因为这部分Log目前不需要落盘
// TODO: DEBUG环境监测来自动化本变量
const SHOW_DEBUG_LOG = false;
const typeAheadLogger = (...message) => {
  if (SHOW_DEBUG_LOG) {
    console.log(message);
  }
};

const enum CursorMoveDirection {
  Back = 'D',
  Forwards = 'C',
}

interface ICoordinate {
  x: number;
  y: number;
  baseY: number;
}

class Cursor implements ICoordinate {
  private _x = 0;
  private _y = 1;
  private _baseY = 1;

  get x() {
    return this._x;
  }

  get y() {
    return this._y;
  }

  get baseY() {
    return this._baseY;
  }

  get coordinate(): ICoordinate {
    return { x: this._x, y: this._y, baseY: this._baseY };
  }

  constructor(
    readonly rows: number,
    readonly cols: number,
    private readonly _buffer: IBuffer
  ) {
    this._x = _buffer.cursorX;
    this._y = _buffer.cursorY;
    this._baseY = _buffer.baseY;
  }

  getLine() {
    return this._buffer.getLine(this._y + this._baseY);
  }

  getCell(loadInto?: IBufferCell) {
    return this.getLine()?.getCell(this._x, loadInto);
  }

  moveTo(coordinate: ICoordinate) {
    this._x = coordinate.x;
    this._y = coordinate.y + coordinate.baseY - this._baseY;
    return this.moveInstruction();
  }

  clone() {
    const c = new Cursor(this.rows, this.cols, this._buffer);
    c.moveTo(this);
    return c;
  }

  move(x: number, y: number) {
    this._x = x;
    this._y = y;
    return this.moveInstruction();
  }

  shift(x: number = 0, y: number = 0) {
    this._x += x;
    this._y += y;
    return this.moveInstruction();
  }

  moveInstruction() {
    // 如果 y 坐标大于xterm的rows(一屏显示行数), 做一下额外处理
    if (this._y >= this.rows) {
      this._baseY += this._y - (this.rows - 1);
      this._y = this.rows - 1;
    } else if (this._y < 0) {
      this._baseY -= this._y;
      this._y = 0;
    }

    // 坐标都加1，因为xterm的cursorX,Y是从0开始，而CSI的坐标控制是从1开始
    return `${CSI}${this._y + 1};${this._x + 1}H`;
  }
}

const moveToWordBoundary = (b: IBuffer, cursor: Cursor, direction: -1 | 1) => {
  let ateLeadingWhitespace = false;
  if (direction < 0) {
    cursor.shift(-1);
  }

  let cell: IBufferCell | undefined;
  while (cursor.x >= 0) {
    cell = cursor.getCell(cell);
    if (!cell?.getCode()) {
      return;
    }

    const chars = cell.getChars();
    if (NOT_WORD_RE.test(chars)) {
      if (ateLeadingWhitespace) {
        break;
      }
    } else {
      ateLeadingWhitespace = true;
    }

    cursor.shift(direction);
  }

  if (direction < 0) {
    cursor.shift(1); // we want to place the cursor after the whitespace starting the word
  }
};

const enum MatchResult {
  /** matched successfully */
  Success,
  /** failed to match */
  Failure,
  /** buffer data, it might match in the future one more data comes in */
  Buffer,
}

export interface IPrediction {
  /**
   * Whether applying this prediction can modify the style attributes of the
   * terminal. If so it means we need to reset the cursor style if it's
   * rolled back.
   */
  readonly affectsStyle?: boolean;

  /**
   * If set to false, the prediction will not be cleared if no input is
   * received from the server.
   */
  readonly clearAfterTimeout?: boolean;

  /**
   * Returns a sequence to apply the prediction.
   * @param buffer to write to
   * @param cursor position to write the data. Should advance the cursor.
   * @returns a string to be written to the user terminal, or optionally a
   * string for the user terminal and real pty.
   */
  apply(buffer: IBuffer, cursor: Cursor): string;

  /**
   * Returns a sequence to roll back a previous `apply()` call. If
   * `rollForwards` is not given, then this is also called if a prediction
   * is correct before show the user's data.
   */
  rollback(cursor: Cursor): string;

  /**
   * If available, this will be called when the prediction is correct.
   */
  rollForwards(cursor: Cursor, withInput: string): string;

  /**
   * Returns whether the given input is one expected by this prediction.
   * @param input reader for the input the PTY is giving
   * @param lookBehind the last successfully-made prediction, if any
   */
  matches(input: StringReader, lookBehind?: IPrediction): MatchResult;
}

class StringReader {
  index = 0;

  get remaining() {
    return this._input.length - this.index;
  }

  get eof() {
    return this.index === this._input.length;
  }

  get rest() {
    return this._input.slice(this.index);
  }

  constructor(private readonly _input: string) {}

  /**
   * Advances the reader and returns the character if it matches.
   */
  eatChar(char: string) {
    if (this._input[this.index] !== char) {
      return;
    }

    this.index++;
    return char;
  }

  /**
   * Advances the reader and returns the string if it matches.
   */
  eatStr(substr: string) {
    if (this._input.slice(this.index, substr.length) !== substr) {
      return;
    }

    this.index += substr.length;
    return substr;
  }

  /**
   * Matches and eats the substring character-by-character. If EOF is reached
   * before the substring is consumed, it will buffer. Index is not moved
   * if it's not a match.
   */
  eatGradually(substr: string): MatchResult {
    const prevIndex = this.index;
    for (let i = 0; i < substr.length; i++) {
      if (i > 0 && this.eof) {
        return MatchResult.Buffer;
      }

      if (!this.eatChar(substr[i])) {
        this.index = prevIndex;
        return MatchResult.Failure;
      }
    }

    return MatchResult.Success;
  }

  /**
   * Advances the reader and returns the regex if it matches.
   */
  eatRe(re: RegExp) {
    const match = re.exec(this._input.slice(this.index));
    if (!match) {
      return;
    }

    this.index += match[0].length;
    return match;
  }

  /**
   * Advances the reader and returns the character if the code matches.
   */
  eatCharCode(min = 0, max = min + 1) {
    const code = this._input.charCodeAt(this.index);
    if (code < min || code >= max) {
      return undefined;
    }

    this.index++;
    return code;
  }
}
/**
 * Wraps another prediction. Does not apply the prediction, but will pass
 * through its `matches` request.
 */
class TentativeBoundary implements IPrediction {
  private _appliedCursor?: Cursor;

  constructor(readonly inner: IPrediction) {}

  apply(buffer: IBuffer, cursor: Cursor) {
    this._appliedCursor = cursor.clone();
    this.inner.apply(buffer, this._appliedCursor);
    return '';
  }

  rollback(cursor: Cursor) {
    this.inner.rollback(cursor.clone());
    return '';
  }

  rollForwards(cursor: Cursor, withInput: string) {
    if (this._appliedCursor) {
      cursor.moveTo(this._appliedCursor);
    }

    return withInput;
  }

  matches(input: StringReader) {
    return this.inner.matches(input);
  }
}
/**
 * Prediction for a single alphanumeric character.
 */
class CharacterPrediction implements IPrediction {
  readonly affectsStyle = true;

  appliedAt?: {
    pos: ICoordinate;
    oldAttributes: string;
    oldChar: string;
  };

  constructor(
    private readonly _style: TypeAheadStyle,
    private readonly _char: string
  ) {}

  apply(_: IBuffer, cursor: Cursor) {
    const cell = cursor.getCell();
    // 检查光标位置是否有字符和相关的样式，如果有的话，就先把那个字符和相关信息存下来，用于后续可能的回滚
    // 同时储存当前的光标，同样用于后续的RollForwards/RollBack
    this.appliedAt = cell
      ? {
          pos: cursor.coordinate,
          oldAttributes: attributesToSeq(cell),
          oldChar: cell.getChars(),
        }
      : { pos: cursor.coordinate, oldAttributes: '', oldChar: '' };

    cursor.shift(1);

    // eg. character l -> \x1B[2ml\x1B[22m
    return this._style.apply + this._char + this._style.undo;
  }

  rollback(cursor: Cursor) {
    if (!this.appliedAt) {
      return ''; // not applied
    }

    const { oldAttributes, oldChar, pos } = this.appliedAt;
    const r =
      cursor.moveTo(pos) +
      (oldChar
        ? `${oldAttributes}${oldChar}${cursor.moveTo(pos)}`
        : DELETE_CHAR);
    return r;
  }

  rollForwards(cursor: Cursor, input: string) {
    if (!this.appliedAt) {
      return ''; // not applied
    }
    return cursor.clone().moveTo(this.appliedAt.pos) + input;
  }

  matches(input: StringReader, lookBehind?: IPrediction) {
    const startIndex = input.index;

    // remove any styling CSI before checking the char
    while (input.eatRe(CSI_STYLE_RE)) {}

    if (input.eof) {
      return MatchResult.Buffer;
    }

    if (input.eatChar(this._char)) {
      return MatchResult.Success;
    }

    if (lookBehind instanceof CharacterPrediction) {
      // see #112842
      const sillyZshOutcome = input.eatGradually(
        `\b${lookBehind._char}${this._char}`
      );
      if (sillyZshOutcome !== MatchResult.Failure) {
        return sillyZshOutcome;
      }
    }

    input.index = startIndex;
    return MatchResult.Failure;
  }
}

class BackspacePrediction implements IPrediction {
  protected _appliedAt?: {
    pos: ICoordinate;
    oldAttributes: string;
    oldChar: string;
    isLastChar: boolean;
  };

  constructor(private readonly _terminal: Terminal) {}

  apply(_: IBuffer, cursor: Cursor) {
    // at eol if everything to the right is whitespace (zsh will emit a "clear line" code in this case)
    // todo: can be optimized if `getTrimmedLength` is exposed from xterm
    const isLastChar = !cursor
      .getLine()
      ?.translateToString(undefined, cursor.x)
      .trim();
    const pos = cursor.coordinate;
    const move = cursor.shift(-1);
    const cell = cursor.getCell();
    this._appliedAt = cell
      ? {
          isLastChar,
          pos,
          oldAttributes: attributesToSeq(cell),
          oldChar: cell.getChars(),
        }
      : { isLastChar, pos, oldAttributes: '', oldChar: '' };

    return move + DELETE_CHAR;
  }

  rollback(cursor: Cursor) {
    if (!this._appliedAt) {
      return ''; // not applied
    }

    const { oldAttributes, oldChar, pos } = this._appliedAt;
    if (!oldChar) {
      return cursor.moveTo(pos) + DELETE_CHAR;
    }

    return (
      oldAttributes +
      oldChar +
      cursor.moveTo(pos) +
      attributesToSeq(core(this._terminal)._inputHandler._curAttrData)
    );
  }

  rollForwards() {
    return '';
  }

  matches(input: StringReader) {
    if (this._appliedAt?.isLastChar) {
      const r1 = input.eatGradually(`\b${CSI}K`);
      if (r1 !== MatchResult.Failure) {
        return r1;
      }

      const r2 = input.eatGradually(`\b \b`);
      if (r2 !== MatchResult.Failure) {
        return r2;
      }
    }

    return MatchResult.Failure;
  }
}

class NewlinePrediction implements IPrediction {
  protected _prevPosition?: ICoordinate;

  apply(_: IBuffer, cursor: Cursor) {
    this._prevPosition = cursor.coordinate;
    cursor.move(0, cursor.y + 1);
    return '\r\n';
  }

  rollback(cursor: Cursor) {
    return this._prevPosition ? cursor.moveTo(this._prevPosition) : '';
  }

  rollForwards() {
    return ''; // does not need to rewrite
  }

  matches(input: StringReader) {
    return input.eatGradually('\r\n');
  }
}

/**
 * Prediction when the cursor reaches the end of the line. Similar to newline
 * prediction, but shells handle it slightly differently.
 */
class LinewrapPrediction extends NewlinePrediction implements IPrediction {
  override apply(_: IBuffer, cursor: Cursor) {
    this._prevPosition = cursor.coordinate;
    cursor.move(0, cursor.y + 1);
    return ' \r';
  }

  override matches(input: StringReader) {
    // bash and zshell add a space which wraps in the terminal, then a CR
    const r = input.eatGradually(' \r');
    if (r !== MatchResult.Failure) {
      // zshell additionally adds a clear line after wrapping to be safe -- eat it
      const r2 = input.eatGradually(DELETE_REST_OF_LINE);
      return r2 === MatchResult.Buffer ? MatchResult.Buffer : r;
    }

    return input.eatGradually('\r\n');
  }
}

class CursorMovePrediction implements IPrediction {
  private _applied?: {
    rollForward: string;
    prevPosition: number;
    prevAttrs: string;
    amount: number;
  };

  constructor(
    private readonly _direction: CursorMoveDirection,
    private readonly _moveByWords: boolean,
    private readonly _amount: number
  ) {}

  apply(buffer: IBuffer, cursor: Cursor) {
    const prevPosition = cursor.x;
    const currentCell = cursor.getCell();
    const prevAttrs = currentCell ? attributesToSeq(currentCell) : '';

    const {
      _amount: amount,
      _direction: direction,
      _moveByWords: moveByWords,
    } = this;
    const delta = direction === CursorMoveDirection.Back ? -1 : 1;

    const target = cursor.clone();
    if (moveByWords) {
      for (let i = 0; i < amount; i++) {
        moveToWordBoundary(buffer, target, delta);
      }
    } else {
      target.shift(delta * amount);
    }

    this._applied = {
      amount: Math.abs(cursor.x - target.x),
      prevPosition,
      prevAttrs,
      rollForward: cursor.moveTo(target),
    };

    return this._applied.rollForward;
  }

  rollback(cursor: Cursor) {
    if (!this._applied) {
      return '';
    }

    return (
      cursor.move(this._applied.prevPosition, cursor.y) +
      this._applied.prevAttrs
    );
  }

  rollForwards() {
    return ''; // does not need to rewrite
  }

  matches(input: StringReader) {
    if (!this._applied) {
      return MatchResult.Failure;
    }

    const direction = this._direction;
    const { amount, rollForward } = this._applied;

    // arg can be omitted to move one character. We don't eatGradually() here
    // or below moves that don't go as far as the cursor would be buffered
    // indefinitely
    if (input.eatStr(`${CSI}${direction}`.repeat(amount))) {
      return MatchResult.Success;
    }

    // \b is the equivalent to moving one character back
    if (direction === CursorMoveDirection.Back) {
      if (input.eatStr(`\b`.repeat(amount))) {
        return MatchResult.Success;
      }
    }

    // check if the cursor position is set absolutely
    if (rollForward) {
      const r = input.eatGradually(rollForward);
      if (r !== MatchResult.Failure) {
        return r;
      }
    }

    // check for a relative move in the direction
    return input.eatGradually(`${CSI}${amount}${direction}`);
  }
}

export class PredictionStats extends Disposable {
  private readonly _stats: [latency: number, correct: boolean][] = [];
  private _index = 0;
  private readonly _addedAtTime = new WeakMap<IPrediction, number>();
  private readonly _changeEmitter = new Emitter<void>();
  readonly onChange = this._changeEmitter.event;

  /**
   * Gets the percent (0-1) of predictions that were accurate.
   */
  get accuracy() {
    let correctCount = 0;
    for (const [, correct] of this._stats) {
      if (correct) {
        correctCount++;
      }
    }

    return correctCount / (this._stats.length || 1);
  }

  /**
   * Gets the number of recorded stats.
   */
  get sampleSize() {
    return this._stats.length;
  }

  /**
   * Gets latency stats of successful predictions.
   */
  get latency() {
    const latencies = this._stats
      .filter(([, correct]) => correct)
      .map(([s]) => s)
      .sort();

    return {
      count: latencies.length,
      min: latencies[0],
      median: latencies[Math.floor(latencies.length / 2)],
      max: latencies[latencies.length - 1],
    };
  }

  /**
   * Gets the maximum observed latency.
   */
  get maxLatency() {
    let max = -Infinity;
    for (const [latency, correct] of this._stats) {
      if (correct) {
        max = Math.max(latency, max);
      }
    }

    return max;
  }

  constructor(timeline: PredictionTimeline) {
    super();
    this.addDispose(
      timeline.onPredictionAdded((p) => this._addedAtTime.set(p, Date.now()))
    );
    this.addDispose(
      timeline.onPredictionSucceeded(this._pushStat.bind(this, true))
    );
    this.addDispose(
      timeline.onPredictionFailed(this._pushStat.bind(this, false))
    );
  }

  private _pushStat(correct: boolean, prediction: IPrediction) {
    const started = this._addedAtTime.get(prediction)!;
    this._stats[this._index] = [Date.now() - started, correct];
    this._index = (this._index + 1) % statsBufferSize;
    this._changeEmitter.fire();
  }
}

export class PredictionTimeline {
  /**
   * Expected queue of events. Only predictions for the lowest are
   * written into the terminal.
   */
  private _expected: { gen: number; p: IPrediction }[] = [];

  /**
   * Current prediction generation.
   */
  private _currentGen = 0;

  /**
   * Current cursor position -- kept outside the buffer since it can be ahead
   * if typing swiftly. The position of the cursor that the user is currently
   * looking at on their screen (or will be looking at after all pending writes
   * are flushed.)
   */
  private _physicalCursor: Cursor | undefined;

  /**
   * Cursor position taking into account all (possibly not-yet-applied)
   * predictions. A new prediction inserted, if applied, will be applied at
   * the position of the tentative cursor.
   */
  private _tenativeCursor: Cursor | undefined;

  /**
   * Previously sent data that was buffered and should be prepended to the
   * next input.
   */
  private _inputBuffer?: string;

  /**
   * Whether predictions are echoed to the terminal. If false, predictions
   * will still be computed internally for latency metrics, but input will
   * never be adjusted.
   */
  private _showPredictions = false;

  /**
   * The last successfully-made prediction.
   */
  private _lookBehind?: IPrediction;

  private readonly _addedEmitter = new Emitter<IPrediction>();
  readonly onPredictionAdded = this._addedEmitter.event;
  private readonly _failedEmitter = new Emitter<IPrediction>();
  readonly onPredictionFailed = this._failedEmitter.event;
  private readonly _succeededEmitter = new Emitter<IPrediction>();
  readonly onPredictionSucceeded = this._succeededEmitter.event;

  private get _currentGenerationPredictions() {
    return this._expected
      .filter(({ gen }) => gen === this._expected[0].gen)
      .map(({ p }) => p);
  }

  get isShowingPredictions() {
    return this._showPredictions;
  }

  get length() {
    return this._expected.length;
  }

  constructor(
    readonly terminal: Terminal,
    private readonly _style: TypeAheadStyle
  ) {}

  setShowPredictions(show: boolean) {
    if (show === this._showPredictions) {
      return;
    }

    typeAheadLogger('set predictions:', show);
    this._showPredictions = show;

    const buffer = this._getActiveBuffer();
    if (!buffer) {
      return;
    }

    const toApply = this._currentGenerationPredictions;
    if (show) {
      this.clearCursor();
      this._style.expectIncomingStyle(
        toApply.reduce((count, p) => (p.affectsStyle ? count + 1 : count), 0)
      );
      this.terminal.write(
        toApply
          .map((p) => p.apply(buffer, this.physicalCursor(buffer)))
          .join('')
      );
    } else {
      this.terminal.write(
        toApply
          .reverse()
          .map((p) => p.rollback(this.physicalCursor(buffer)))
          .join('')
      );
    }
  }

  /**
   * Undoes any predictions written and resets expectations.
   */
  undoAllPredictions() {
    const buffer = this._getActiveBuffer();
    if (this._showPredictions && buffer) {
      this.terminal.write(
        this._currentGenerationPredictions
          .reverse()
          .map((p) => p.rollback(this.physicalCursor(buffer)))
          .join('')
      );
    }

    this._expected = [];
  }

  /**
   * Should be called when input is incoming to the temrinal.
   */
  beforeServerInput(input: string): string {
    const originalInput = input;
    if (this._inputBuffer) {
      input = this._inputBuffer + input;
      this._inputBuffer = undefined;
    }

    if (!this._expected.length) {
      this._clearPredictionState();
      return input;
    }

    const buffer = this._getActiveBuffer();
    if (!buffer) {
      this._clearPredictionState();
      return input;
    }

    let output = '';

    const reader = new StringReader(input);
    const startingGen = this._expected[0].gen;
    const emitPredictionOmitted = () => {
      const omit = reader.eatRe(PREDICTION_OMIT_RE);
      if (omit) {
        output += omit[0];
      }
    };

    ReadLoop: while (this._expected.length && reader.remaining > 0) {
      emitPredictionOmitted();

      const { p: prediction, gen } = this._expected[0];
      const cursor = this.physicalCursor(buffer);
      const beforeTestReaderIndex = reader.index;
      switch (prediction.matches(reader, this._lookBehind)) {
        case MatchResult.Success: {
          // if the input character matches what the next prediction expected, undo
          // the prediction and write the real character out.
          const eaten = input.slice(beforeTestReaderIndex, reader.index);
          if (gen === startingGen) {
            output += prediction.rollForwards?.(cursor, eaten);
          } else {
            prediction.apply(buffer, this.physicalCursor(buffer)); // move cursor for additional apply
            output += eaten;
          }

          this._succeededEmitter.fire(prediction);
          this._lookBehind = prediction;
          this._expected.shift();
          break;
        }
        case MatchResult.Buffer:
          // on a buffer, store the remaining data and completely read data
          // to be output as normal.
          this._inputBuffer = input.slice(beforeTestReaderIndex);
          reader.index = input.length;
          break ReadLoop;
        case MatchResult.Failure: {
          // on a failure, roll back all remaining items in this generation
          // and clear predictions, since they are no longer valid
          const rollback = this._expected
            .filter((p) => p.gen === startingGen)
            .reverse();
          output += rollback
            .map(({ p }) => p.rollback(this.physicalCursor(buffer)))
            .join('');
          if (rollback.some((r) => r.p.affectsStyle)) {
            // reading the current style should generally be safe, since predictions
            // always restore the style if they modify it.
            output += attributesToSeq(
              core(this.terminal)._inputHandler._curAttrData
            );
          }
          this._clearPredictionState();
          this._failedEmitter.fire(prediction);
          break ReadLoop;
        }
      }
    }

    emitPredictionOmitted();

    // Extra data (like the result of running a command) should cause us to
    // reset the cursor
    if (!reader.eof) {
      output += reader.rest;
      this._clearPredictionState();
    }

    // If we passed a generation boundary, apply the current generation's predictions
    if (this._expected.length && startingGen !== this._expected[0].gen) {
      for (const { p, gen } of this._expected) {
        if (gen !== this._expected[0].gen) {
          break;
        }
        if (p.affectsStyle) {
          this._style.expectIncomingStyle();
        }

        output += p.apply(buffer, this.physicalCursor(buffer));
      }
    }

    if (!this._showPredictions) {
      return originalInput;
    }

    if (output.length === 0 || output === input) {
      return output;
    }

    if (this._physicalCursor) {
      output += this._physicalCursor.moveInstruction();
    }

    // prevent cursor flickering while typing
    output = HIDE_CURSOR + output + SHOW_CURSOR;

    return output;
  }

  /**
   * Clears any expected predictions and stored state. Should be called when
   * the pty gives us something we don't recognize.
   */
  private _clearPredictionState() {
    this._expected = [];
    this.clearCursor();
    this._lookBehind = undefined;
  }

  /**
   * Appends a typeahead prediction.
   */
  addPrediction(buffer: IBuffer, prediction: IPrediction) {
    typeAheadLogger(
      'prediction type: \x1b[36m%s\x1b[0m',
      prediction.constructor.name
    );
    // if (prediction.constructor.name === 'TentativeBoundary') {
    //   console.log('prediction type inner: \x1b[36m%s\x1b[0m', prediction['inner'].constructor.name);
    // }
    this._expected.push({ gen: this._currentGen, p: prediction });
    this._addedEmitter.fire(prediction);

    if (this._currentGen !== this._expected[0].gen) {
      prediction.apply(buffer, this.tentativeCursor(buffer));
      return false;
    }

    const text = prediction.apply(buffer, this.physicalCursor(buffer));
    this._tenativeCursor = undefined; // next read will get or clone the physical cursor

    if (this._showPredictions && text) {
      if (prediction.affectsStyle) {
        this._style.expectIncomingStyle();
      }
      typeAheadLogger('predict:', JSON.stringify(text));
      typeAheadLogger(
        'prediction type: \x1b[36m%s\x1b[0m',
        prediction.constructor.name
      );
      this.terminal.write(text);
    }

    return true;
  }

  /**
   * Appends a prediction followed by a boundary. The predictions applied
   * after this one will only be displayed after the give prediction matches
   * pty output/
   */
  addBoundary(): void;
  addBoundary(buffer: IBuffer, prediction: IPrediction): boolean;
  addBoundary(buffer?: IBuffer, prediction?: IPrediction) {
    let applied = false;
    if (buffer && prediction) {
      // We apply the prediction so that it's matched against, but wrapped
      // in a tentativeboundary so that it doesn't affect the physical cursor.
      // Then we apply it specifically to the tentative cursor.
      applied = this.addPrediction(buffer, new TentativeBoundary(prediction));
      prediction.apply(buffer, this.tentativeCursor(buffer));
    }
    this._currentGen++;
    return applied;
  }

  /**
   * Peeks the last prediction written.
   */
  peekEnd(): IPrediction | undefined {
    return this._expected[this._expected.length - 1]?.p;
  }

  /**
   * Peeks the first pending prediction.
   */
  peekStart(): IPrediction | undefined {
    return this._expected[0]?.p;
  }

  /**
   * Current position of the cursor in the terminal.
   */
  physicalCursor(buffer: IBuffer) {
    if (!this._physicalCursor) {
      if (this._showPredictions) {
        flushOutput(this.terminal);
      }
      this._physicalCursor = new Cursor(
        this.terminal.rows,
        this.terminal.cols,
        buffer
      );
    }

    return this._physicalCursor;
  }

  /**
   * Cursor position if all predictions and boundaries that have been inserted
   * so far turn out to be successfully predicted.
   */
  tentativeCursor(buffer: IBuffer) {
    if (!this._tenativeCursor) {
      this._tenativeCursor = this.physicalCursor(buffer).clone();
    }

    return this._tenativeCursor;
  }

  clearCursor() {
    this._physicalCursor = undefined;
    this._tenativeCursor = undefined;
  }

  private _getActiveBuffer() {
    const buffer = this.terminal.buffer.active;
    return buffer.type === 'normal' ? buffer : undefined;
  }
}

/**
 * Gets the escape sequence args to restore state/appearance in the cell.
 */
const attributesToArgs = (cell: XtermAttributes) => {
  if (cell.isAttributeDefault()) {
    return [0];
  }

  const args: any[] = [];
  if (cell.isBold()) {
    args.push(1);
  }
  if (cell.isDim()) {
    args.push(2);
  }
  if (cell.isItalic()) {
    args.push(3);
  }
  if (cell.isUnderline()) {
    args.push(4);
  }
  if (cell.isBlink()) {
    args.push(5);
  }
  if (cell.isInverse()) {
    args.push(7);
  }
  if (cell.isInvisible()) {
    args.push(8);
  }

  if (cell.isFgRGB()) {
    args.push(
      38,
      2,
      cell.getFgColor() >>> 24,
      (cell.getFgColor() >>> 16) & 0xff,
      cell.getFgColor() & 0xff
    );
  }
  if (cell.isFgPalette()) {
    args.push(38, 5, cell.getFgColor());
  }
  if (cell.isFgDefault()) {
    args.push(39);
  }

  if (cell.isBgRGB()) {
    args.push(
      48,
      2,
      cell.getBgColor() >>> 24,
      (cell.getBgColor() >>> 16) & 0xff,
      cell.getBgColor() & 0xff
    );
  }
  if (cell.isBgPalette()) {
    args.push(48, 5, cell.getBgColor());
  }
  if (cell.isBgDefault()) {
    args.push(49);
  }

  return args;
};

/**
 * Gets the escape sequence to restore state/appearance in the cell.
 */
const attributesToSeq = (cell: XtermAttributes) =>
  `${CSI}${attributesToArgs(cell).join(';')}m`;

const arrayHasPrefixAt = <T>(
  a: ReadonlyArray<T>,
  ai: number,
  b: ReadonlyArray<T>
) => {
  if (a.length - ai > b.length) {
    return false;
  }

  for (let bi = 0; bi < b.length; bi++, ai++) {
    if (b[ai] !== a[ai]) {
      return false;
    }
  }

  return true;
};

/**
 * @see https://github.com/xtermjs/xterm.js/blob/065eb13a9d3145bea687239680ec9696d9112b8e/src/common/InputHandler.ts#L2127
 */
const getColorWidth = (params: (number | number[])[], pos: number) => {
  const accu = [0, 0, -1, 0, 0, 0];
  let cSpace = 0;
  let advance = 0;

  do {
    const v = params[pos + advance];
    accu[advance + cSpace] = typeof v === 'number' ? v : v[0];
    if (typeof v !== 'number') {
      let i = 0;
      do {
        if (accu[1] === 5) {
          cSpace = 1;
        }
        accu[advance + i + 1 + cSpace] = v[i];
      } while (++i < v.length && i + advance + 1 + cSpace < accu.length);
      break;
    }
    // exit early if can decide color mode with semicolons
    if (
      (accu[1] === 5 && advance + cSpace >= 2) ||
      (accu[1] === 2 && advance + cSpace >= 5)
    ) {
      break;
    }
    // offset colorSpace slot for semicolon mode
    if (accu[1]) {
      cSpace = 1;
    }
  } while (++advance + pos < params.length && advance + cSpace < accu.length);

  return advance;
};

class TypeAheadStyle implements IDisposable {
  private static _compileArgs(args: ReadonlyArray<number>) {
    return `${CSI}${args.join(';')}m`;
  }

  /**
   * Number of typeahead style arguments we expect to read. If this is 0 and
   * we see a style coming in, we know that the PTY actually wanted to update.
   */
  private _expectedIncomingStyles = 0;
  private _applyArgs!: ReadonlyArray<number>;
  private _originalUndoArgs!: ReadonlyArray<number>;
  private _undoArgs!: ReadonlyArray<number>;

  apply!: string;
  undo!: string;
  private _csiHandler?: IDisposable;

  constructor(
    value: ITerminalConfiguration['localEchoStyle'],
    private readonly _terminal: Terminal
  ) {
    this.onUpdate(value);
  }

  /**
   * Signals that a style was written to the terminal and we should watch
   * for it coming in.
   */
  expectIncomingStyle(n = 1) {
    this._expectedIncomingStyles += n * 2;
  }

  /**
   * Starts tracking for CSI changes in the terminal.
   */
  startTracking() {
    this._expectedIncomingStyles = 0;
    this._onDidWriteSGR(
      attributesToArgs(core(this._terminal)._inputHandler._curAttrData)
    );
    this._csiHandler = this._terminal.parser.registerCsiHandler(
      { final: 'm' },
      (args) => {
        this._onDidWriteSGR(args);
        return false;
      }
    );
  }

  /**
   * Stops tracking terminal CSI changes.
   */
  @debounce(2000)
  debounceStopTracking() {
    this._stopTracking();
  }

  /**
   * @inheritdoc
   */
  dispose() {
    this._stopTracking();
  }

  private _stopTracking() {
    this._csiHandler?.dispose();
    this._csiHandler = undefined;
  }

  private _onDidWriteSGR(args: (number | number[])[]) {
    const originalUndo = this._undoArgs;
    for (let i = 0; i < args.length; ) {
      const px = args[i];
      const p = typeof px === 'number' ? px : px[0];

      if (this._expectedIncomingStyles) {
        if (arrayHasPrefixAt(args, i, this._undoArgs)) {
          this._expectedIncomingStyles--;
          i += this._undoArgs.length;
          continue;
        }
        if (arrayHasPrefixAt(args, i, this._applyArgs)) {
          this._expectedIncomingStyles--;
          i += this._applyArgs.length;
          continue;
        }
      }

      const width =
        p === 38 || p === 48 || p === 58 ? getColorWidth(args, i) : 1;
      switch (this._applyArgs[0]) {
        case 1:
          if (p === 2) {
            this._undoArgs = [22, 2];
          } else if (p === 22 || p === 0) {
            this._undoArgs = [22];
          }
          break;
        case 2:
          if (p === 1) {
            this._undoArgs = [22, 1];
          } else if (p === 22 || p === 0) {
            this._undoArgs = [22];
          }
          break;
        case 38:
          if (p === 0 || p === 39 || p === 100) {
            this._undoArgs = [39];
          } else if ((p >= 30 && p <= 38) || (p >= 90 && p <= 97)) {
            this._undoArgs = args.slice(i, i + width) as number[];
          }
          break;
        default:
          if (p === this._applyArgs[0]) {
            this._undoArgs = this._applyArgs;
          } else if (p === 0) {
            this._undoArgs = this._originalUndoArgs;
          }
        // no-op
      }

      i += width;
    }

    if (originalUndo !== this._undoArgs) {
      this.undo = TypeAheadStyle._compileArgs(this._undoArgs);
    }
  }

  /**
   * Updates the current typeahead style.
   */
  onUpdate(style: ITerminalConfiguration['localEchoStyle']) {
    const { applyArgs, undoArgs } = this._getArgs(style);
    this._applyArgs = applyArgs;
    this._undoArgs = this._originalUndoArgs = undoArgs;
    this.apply = TypeAheadStyle._compileArgs(this._applyArgs);
    this.undo = TypeAheadStyle._compileArgs(this._undoArgs);
  }

  private _getArgs(style: ITerminalConfiguration['localEchoStyle']) {
    switch (style) {
      case 'bold':
        return { applyArgs: [1], undoArgs: [22] };
      case 'dim':
        return { applyArgs: [2], undoArgs: [22] };
      case 'italic':
        return { applyArgs: [3], undoArgs: [23] };
      case 'underlined':
        return { applyArgs: [4], undoArgs: [24] };
      case 'inverted':
        return { applyArgs: [7], undoArgs: [27] };
      default: {
        let color: Color;
        try {
          color = Color.fromHex(style);
        } catch (_e) {
          color = new Color(new RGBA(255, 0, 0, 1));
        }

        const { r, g, b } = color.rgba;
        return { applyArgs: [38, 2, r, g, b], undoArgs: [39] };
      }
    }
  }
}
